package com.feiuxiu.datastructure.array;

import java.util.Arrays;

import static com.feiuxiu.uitls.ArraysUtils.*;

/**
 * title: 稀疏数组测试（二维）
 * notes: 所谓稀疏数组，就是对一个普通的数组中的元素进行压缩，可以有多维的，这里哪二维举例
 * 一个二维数组，把其中的非零元素统计出来，放在一个 n*3的二维数组之中，  3列中  0：行  1：列  2：值
 * 第一行 存储的是 原数组的行数和列数
 * author: feixiu
 * date:2025/9/1 21:32
 */
public class SparseArray {


    public static void main(String[] args) {
        //测试
        int[][] testArray = new int[11][11];
        testArray[1][2] = 1;
        testArray[2][3] = 2;
        testArray[4][5] = 2;
        System.out.println("原数组");
        printTwoArrayWithRow(testArray);
        int[][] sparseArray = toSparseArray(testArray);
        System.out.println("稀疏数组");
        printTwoArray(sparseArray);
        int[][] commonArray = sparseToCommon(sparseArray);
        System.out.println("还原之后的数组");
        printTwoArrayWithRow(commonArray);
    }


    /**
     * 把原数组 转为稀疏数组
     * @param sourceArray 原数组
     * @return 稀疏数组
     */
    public static int[][] toSparseArray(int[][] sourceArray){
        if (sourceArray==null||sourceArray[0]==null){
            throw new RuntimeException("原数组为空");
        }
        // 构建稀疏数组，第一行记录原数组的行数和列数,需要先获取原数组中不为0的元素的个数
        int row=0;
        int arrayRow=sourceArray.length;
        for (int[] ints : sourceArray) {
            for (int anInt : ints) {
                if (anInt != 0) {
                    row++;
                }
            }
        }
        int arrayColumn=sourceArray[0].length;
        int[][] sparseArray=new int[row+1][3];
        sparseArray[0][0]=arrayRow;
        sparseArray[0][1]=arrayColumn;

        // 遍历原数组，并存入稀疏数组
        int targetRow=1;
        for (int i = 0; i < sourceArray.length; i++) {
            for (int j = 0; j < sourceArray[i].length; j++) {
                if (sourceArray[i][j]!=0){
                    sparseArray[targetRow][0]=i;//存入行
                    sparseArray[targetRow][1]=j;//存入列
                    sparseArray[targetRow][2]=sourceArray[i][j];//存入值
                    targetRow++;

                }
            }
        }
        return sparseArray;
    }


    /**
     * 根据稀疏数组还原出原来的数组
     * @param sparseArray 稀疏数组
     * @return 原来的数组
     */
    public static int[][] sparseToCommon(int[][] sparseArray){
        if (sparseArray==null||sparseArray[0]==null){
            throw new RuntimeException("稀疏数组格式不对");
        }

        int[][] commonArray=new int[sparseArray[0][0]][sparseArray[0][1]];
        for (int i = 1; i < sparseArray.length; i++) {
            commonArray[sparseArray[i][0]][sparseArray[i][1]]=sparseArray[i][2];
        }
        return commonArray;
    }
}
